# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """
        if not root:
            return "[]"
        data_list = [root.val]
        que = [root]
        i = 0
        m = 1
        while i < m:
            x = que[i]
            if x:
                que.append(x.left)
                data_list.append(x.left.val if x.left else None)
                que.append(x.right)
                data_list.append(x.right.val if x.right else None)
                m += 2
            i += 1
        while data_list[-1] is None:
            data_list.pop()
        return f"[{','.join(map(lambda x: str(x) if x is not None else 'null', data_list))}]"

    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """
        if not data[1:-1]:
            return None
        data_list = data[1:-1].split(',')
        que = []
        root = TreeNode(int(data_list.pop(0)))
        que.append(root)
        while data_list:
            que_next = []
            while que:
                x = que.pop(0)
                if not data_list:
                    break
                left_v = data_list.pop(0)
                if left_v != 'null':
                    left = TreeNode(int(left_v))
                else:
                    left = None
                x.left = left
                if left:
                    que_next.append(left)
                if not data_list:
                    break
                right_v = data_list.pop(0)
                if right_v != 'null':
                    right = TreeNode(int(right_v))
                else:
                    right = None
                x.right = right
                if right:
                    que_next.append(right)
            que = que_next
        return root


def show(rt: TreeNode, dp=0):
    if not rt:
        print(' '*dp, 'null')
        return
    show(rt.right, dp+1)
    print(' ' * dp, rt.val)
    show(rt.left, dp+1)

# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))


codec = Codec()

d0 = "[1,2,3,null,null,4,5]"
print(d0)
r0 = codec.deserialize(d0)
print(r0)
show(r0)
d00 = codec.serialize(r0)
print(d00)

d1 = "[]"
print(d1)
r1 = codec.deserialize(d1)
print(r1)
show(r1)
d11 = codec.serialize(r1)
print(d11)

d2 = "[-1,0,1]"
print(d2)
r2 = codec.deserialize(d2)
print(r2)
show(r2)
d22 = codec.serialize(r2)
print(d22)

d3 = "[5,2,3,null,null,2,4,3,1]"
print(d3)
r3 = codec.deserialize(d3)
print(r3)
show(r3)
d33 = codec.serialize(r3)
print(d33)

d4 = "[10,9,11,8,null,null,12,7,null,null,13,6,null,null,14,5,null,null,15,4,null,null,16,3,null,null,17,2,null,null,18" \
     ",1,null,null,19,0]"
print(d4)
r4 = codec.deserialize(d4)
print(r4)
show(r4)
d44 = codec.serialize(r4)
print(d44)

